package cn.jdemo.algorithm.backtracking.dfs;

public class MaxAreaOfIsland {
    public static void main(String[] args) {

        int[][] grid = {{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}};
        int res = new MaxAreaOfIsland().maxAreaOfIsland(grid);
        System.out.println(res);
    }

    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        int xlength = grid.length,ylength = grid[0].length;
        for (int i = 0; i < xlength; i++) {
            for (int j = 0; j < ylength; j++) {
                if (grid[i][j] == 1){
                    res = Math.max(res, fill(grid,i,j));
                }
            }
        }
        return res;
    }

    private int fill(int[][] grid, int x, int y) {
        int xlength = grid.length,ylength = grid[0].length;
        if (x<0 || y<0 || x>=xlength || y>=ylength){
            return 0;
        }
        if (grid[x][y]==0){
            return 0;
        }
        grid[x][y]=0;
        return fill(grid,x+1,y)+ fill(grid,x,y+1) + fill(grid,x-1,y) + fill(grid,x,y-1) + 1;
    }
}